package Hot100.Heap;

import java.util.HashMap;
import java.util.PriorityQueue;

public class topKFrequent {
    public static void main(String[] args) {
        int[] nums = {4,1,-1,2,-1,2,3};
        int k = 2;
        int[] result = new topKFrequent().topKFrequent(nums,k);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + "  ");
        }
    }
    public int[] topKFrequent(int[] nums, int k) {
        int[] result = new int[k];
        //定义优先级队列，优先级队列的实现是基于堆的
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        //记录每个数据出现的频次
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i])+1);
            }else {
                map.put(nums[i],1);
            }
        }

        //加入堆中,维持堆中只有k个元素
        for (Integer key : map.keySet()){
            int value = map.get(key);
            if(queue.size() < k){
                queue.add(value);
            }else {
                if(value > queue.peek()){
                    queue.poll();
                    queue.add(value);
                }
            }
        }

        int index = 0;
        while (!queue.isEmpty()){
            for (Integer key : map.keySet()){
                if(map.get(key) == queue.peek()){
                    result[index++] = key;
                    queue.poll();
                }
            }

        }
        return result;
    }
}
